\documentclass{ctexart}

\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{listings}
\usepackage{mathbbol}
\usepackage{fontspec}
\usepackage{caption}
\usepackage{subfigure}

\title{ Project}


\author{姓名:戚宇航 \\ 专业和学号:信息与计算科学  3200104567}

\begin{document}

\maketitle

\section{编译说明}
\noindent
    本次项目作业采用 Makefile 文件对编译进行统一管理。在Makefile所在目录下输入\verb|make report|即可完成编译，得到\verb|report.pdf|，输入\verb|make solveA|即可完成A的程序的编译。 \\ 
    我使用eigen3求解线性方程组，并使用 json file 进行参数输入。
  \subsection*{Function.h}
  \noindent
  \verb|Function|是一个基类，\verb|Function|内是3个纯虚函数，为括号重载，\verb|diff|和\verb|diff2|，用来存储函数的对应点的函数值，一阶导数值和二阶导数值。
  \subsection*{Interpolation.h}
  \noindent
  \verb|Interpolation|是一个基类，\verb|Interpolation|内是2个纯虚函数，为括号重载和\verb|solve()|,分别用来返回对应点的样条插值计算出来的值和计算样条插值。
  \subsection*{Polynomial.h}
  \noindent
  Polynomial是一个用来多项式生成、输入和计算的类。\\
  \noindent $\bullet$ \textbf{class Polynomial}\\
  类Polynomial是用来存储形和计算如$a_0+a_1(x-a)+\dots+a_n(x-a)^n$的多项式。\\
  \noindent $\bullet$ \textbf{class B\_spline}\\
  类B\_spline是为了方便B样条中的计算，利用课本中的\textbf{Definition 3.23}递归计算出样条基函数的值。\\
  \noindent $\bullet$ \textbf{class Input}\\
  类Input是为了在输入为离散的点对应的函数值和导数值等时为了方便设计的类。\\
  \subsection*{spline.h}
  spline.h中有两个类，ppForm\_interpolation和Bspline\_interpolation ，分别实现了\verb|ppFOrm|插值和B样条的分段线性插值和$\mathbb{S}^2_3$样条插值，在输入时用order的值来区分，order的值为1时，为分段线性插值，order的值为3时，为$\mathbb{S}^2_3$样条插值。同时，$\mathbb{S}^2_3$样条插值还支持三种边界条件，分别为complete cubic spline，cubic spline with specified second derivatives at its end points和natural cubic spline三种边界条件，在输入时用Boundary\_conditions来实现区分，Boundary\_conditions为1时，是complete cubic spline，Boundary\_conditions为2时，是cubic spline with specified second derivatives at its end points，Boundary\_conditions为3时，是natural cubic spline。\\
  另外这两个类中都有括号重载和solve()，分别用来返回对应点的样条插值计算出来的值和计算样条插值。括号重载的思路的与之前类似，下面主要分别讲述两个类的solve()函数的设计思路。\\ 
  \noindent $\bullet$ \textbf{class ppForm\_interpolation} \\
  类ppForm\_interpolation的线性插值较为简单，直接利用课本中的\textbf{Lemma 3.3}中的（3.5），（3.6）得到多项式
  \begin{equation}
    p_i(x)=\frac{f(t_{i+1})-f(t_i)}{t_{i+1}-t_i}x + f(t_{i+1})-t_i\frac{f(t_{i+1})-f(t_i)}{t_{i+1}-t_i}.
  \end{equation}
  根据课本中的\textbf{Lemma 3.3}和\textbf{Lemma 3.4}，可以得到三种边界条件分别对应的线性方程组
  $\bullet \;$\verb|complete cubic spline|：
  \begin{equation}
	\begin{bmatrix}
		2         & \mu_2  &           &        &               &                   &           \\
		\lambda_3 & 2      & \mu_3     &        &               &                   &           \\
		          & \ddots & \ddots    & \ddots &               &                   &           \\
		          &        & \lambda_i & 2      & \mu_i         &                   &           \\
		          &        &           & \ddots & \ddots        & \ddots            &           \\
		          &        &           &        & \lambda_{N-2} & 2                 & \mu_{N-2} \\
		          &        &           &        &               & \lambda_{N-1}     & 2         \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		m_2 \\m_3\\ \vdots \\m_i\\ \vdots \\ m_{N-2}\\ m_{N-1}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		b_1-\lambda_2 m_1                                           \\
		b_2                                                         \\
		\vdots                                                      \\
		b_{i-1}                                                     \\
		\vdots                                                      \\
        b_{N-3}-\mu_{N-1}m_{N-1}                                    \\
		b_{N-2}-\mu_{N-1}m_N                                        \\
	\end{bmatrix}
\end{equation}
  
  $\bullet \;$\verb|cubic spline with specified second derivatives at its end points|：
  \begin{equation}
	\begin{bmatrix}
		2         & 1      &           &        &               &                   &           \\
		\lambda_2 & 2      & \mu_2     &        &               &                   &           \\
		          & \ddots & \ddots    & \ddots &               &                   &           \\
		          &        & \lambda_i & 2      & \mu_i         &                   &           \\
		          &        &           & \ddots & \ddots        & \ddots            &           \\
		          &        &           &        & \lambda_{N-1} & 2                 & \mu_{N-1} \\
		          &        &           &        &               & 1                 & 2         \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		m_1 \\m_2\\ \vdots \\m_i\\ \vdots \\ m_{N-1}\\ m_{N}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		b_0                                                         \\
		b_1                                                         \\
		\vdots                                                      \\
		b_{i-1}                                                     \\
		\vdots                                                      \\
        b_{N-2}                                                     \\
		b_N                                                         \\
	\end{bmatrix}
  \end{equation}
  其中\\
  \begin{displaymath}
    \left\{
        \begin{array}{l}
            2m_1+m_2=3f[x_1,x_2]-\frac{x_2-x_1}{2}M_1 :=b_0 \\
            m_{N-1}+2m_{N}=3f[x_{N-1},x_N]+\frac{x_N-x_{N-1}}{2}M_N:=b_N
        \end{array} 
    \right.
  \end{displaymath}
  
  $\bullet \;$\verb|natural cubic spline|：
  \begin{equation}
	\begin{bmatrix}
		2         & 1      &           &        &               &                   &           \\
		\lambda_2 & 2      & \mu_2     &        &               &                   &           \\
		          & \ddots & \ddots    & \ddots &               &                   &           \\
		          &        & \lambda_i & 2      & \mu_i         &                   &           \\
		          &        &           & \ddots & \ddots        & \ddots            &           \\
		          &        &           &        & \lambda_{N-1} & 2                 & \mu_{N-1} \\
		          &        &           &        &               & 1                 & 2         \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		m_1 \\m_2\\ \vdots \\m_i\\ \vdots \\ m_{N-1}\\ m_{N}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		b_0                                                         \\
		b_1                                                         \\
		\vdots                                                      \\
		b_{i-1}                                                     \\
		\vdots                                                      \\
        b_{N-2}                                                     \\
		b_N                                                         \\
	\end{bmatrix}
  \end{equation}
  其中\\
  \begin{displaymath}
    \left\{
        \begin{array}{l}
            2m_1+m_2=3f[x_1,x_2] :=b_0 \\
            m_{N-1}+2m_{N}=3f[x_{N-1},x_N]:=b_N
        \end{array} 
    \right.
\end{displaymath}

  利用eigen3的稀疏矩阵LU分解求解线性方程组$Am = b$得插值点处的导数值$m$从而求得插值函数$S(x)$。 \\
  \noindent $\bullet$ \textbf{class Bspline\_interpolation} \\
  对于线性样条，我添加了两个额外的插值点，$t_1-t_0=t_2-t_1$，$t_{N+1}-t_{N} = t_{N}-t_{N-1}$，然后令
  \begin{equation}
    S(x) = \sum^N_{i=1}a_iB^1_i(x),
\end{equation}
  就得到插值。\\
  对于$\mathbb{S}^2_3$样条，类似地添加插\[x_{2},x_{1},x_{0},x_{N+1},x_{N+2},x_{N+3}.\]再根据下面给出的不同边界条件下的线性方程组求解即可。\\
  $\bullet \;$\verb|complete cubic spline|：
  \begin{equation}
	\begin{bmatrix}
		t_1             & t_2                       &  t_3             &                       &                  &                 &               \\
		B^3_{-1}(x_1)   & B^3_{0}(x_1)              & B^3_1(x_1)       &                       &                  &                 &               \\
		                & \ddots                    & \ddots           & \ddots                &                  &                 &               \\
		                &                           & B^3_{i-2}(x_{i}) & B^3_{i-1}(x_{i})      & B^3_{i}(x_{i})   &                 &               \\
		                &                           &                  & \ddots                & \ddots           & \ddots          &               \\
		                &                           &                  &                       & B^3_{N-2}(x_{N}) & B^3_{N-1}(x_N)  & B^3_{N}(x_N)  \\
		                &                           &                  &                       &t_N               & t_{N+1}         & t_{N+2}       \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		a_{-1} \\a_{-2}\\ \vdots \\a_{i-3}\\ \vdots \\ a_{N-1}\\ a_{N}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		m_1                                                         \\
		f(x_1)                                                      \\
		\vdots                                                      \\
		f(x_i)                                                      \\
		\vdots                                                      \\
        f(x_N)                                                      \\
		m_N                                                         \\
	\end{bmatrix}
  \end{equation}
  其中\\
  \[t_1 = -\frac{3B^2_{0}(x_1)}{x_2 - x_{-1}},\quad t_3 = \frac{3B^2_{1}(x_1)}{x_3 - x_{0}},\quad t_N = -\frac{3B^2_{N-1}(x_N)}{x_{N+1} - x_{N-2}},\quad t_{N+2} = \frac{3B^2_{N}(x_N)}{x_{N+2} - x_{N-1}}\]
\[t_2 = -t_1-t_3, \quad t_{N+1}=-t_{N}-t_{N+2}\]
  $\bullet \;$\verb|cubic spline with specified second derivatives at its end points|：
  \begin{equation}
	\begin{bmatrix}
		t_1             & t_2                       &  t_3             &                       &                  &                 &               \\
		B^3_{-1}(x_1)   & B^3_{0}(x_1)              & B^3_1(x_1)       &                       &                  &                 &               \\
		                & \ddots                    & \ddots           & \ddots                &                  &                 &               \\
		                &                           & B^3_{i-2}(x_{i}) & B^3_{i-1}(x_{i})      & B^3_{i}(x_{i})   &                 &               \\
		                &                           &                  & \ddots                & \ddots           & \ddots          &               \\
		                &                           &                  &                       & B^3_{N-2}(x_{N}) & B^3_{N-1}(x_N)  & B^3_{N}(x_N)  \\
		                &                           &                  &                       &t_N               & t_{N+1}         & t_{N+2}       \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		a_{-1} \\a_{-2}\\ \vdots \\a_{i-3}\\ \vdots \\ a_{N-1}\\ a_{N}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		M_1                                                         \\
		f(x_1)                                                      \\
		\vdots                                                      \\
		f(x_i)                                                      \\
		\vdots                                                      \\
        f(x_N)                                                      \\
		M_N                                                         \\
	\end{bmatrix}
  \end{equation}
  其中\\
  \[t_1 = \frac{6}{(t_2-t_{-1})(t_2-t_0)},\quad t_3 = \frac{6}{(t_3-t_0)(t_2-t_0)}\]
\[t_N = \frac{6}{(t_{N+1}-t_{N-2})(t_{N+1}-t_{N-1})},\quad t_{N+2} = \frac{6}{(t_{N+2}-t_{N-1})(t_{N+1}-t_{N-1})}\]
\[t_2 = -t_1-t_3, \quad t_{N+1}=-t_{N}-t_{N+2}\]
  $\bullet \;$\verb|natural cubic spline|：
  \begin{equation}
	\begin{bmatrix}
		t_1             & t_2                       &  t_3             &                       &                  &                 &               \\
		B^3_{-1}(x_1)   & B^3_{0}(x_1)              & B^3_1(x_1)       &                       &                  &                 &               \\
		                & \ddots                    & \ddots           & \ddots                &                  &                 &               \\
		                &                           & B^3_{i-2}(x_{i}) & B^3_{i-1}(x_{i})      & B^3_{i}(x_{i})   &                 &               \\
		                &                           &                  & \ddots                & \ddots           & \ddots          &               \\
		                &                           &                  &                       & B^3_{N-2}(x_{N}) & B^3_{N-1}(x_N)  & B^3_{N}(x_N)  \\
		                &                           &                  &                       &t_N               & t_{N+1}         & t_{N+2}       \\
	\end{bmatrix}_{}
	\begin{bmatrix}
		a_{-1} \\a_{-2}\\ \vdots \\a_{i-3}\\ \vdots \\ a_{N-1}\\ a_{N}\\
	\end{bmatrix}
	=
	\begin{bmatrix}
		0                                                           \\
		f(x_1)                                                      \\
		\vdots                                                      \\
		f(x_i)                                                      \\
		\vdots                                                      \\
        f(x_N)                                                      \\
		0                                                           \\
	\end{bmatrix}
  \end{equation}
  其中\\
  \[t_1 = \frac{6}{(t_2-t_{-1})(t_2-t_0)},\quad t_3 = \frac{6}{(t_3-t_0)(t_2-t_0)}\]
\[t_N = \frac{6}{(t_{N+1}-t_{N-2})(t_{N+1}-t_{N-1})},\quad t_{N+2} = \frac{6}{(t_{N+2}-t_{N-1})(t_{N+1}-t_{N-1})}\]
\[t_2 = -t_1-t_3, \quad t_{N+1}=-t_{N}-t_{N+2}\]

利用eigen3的稀疏矩阵LU分解求解线性方程组$Am = b$得插值点处的导数值$m$从而求得插值函数$S(x)$。
  \subsection*{Curve\_fitting.h} 
  该头文件内有两个成员函数，为solve()和Get\_Point,可以根据前面样条插值得到的结果，在曲线上取了足够多个点的坐标输出，后面可以根据这些画出图像，solve函数根据课本上的\textbf{Algorithm 3.72}，计算cumulative\_chordal\_lengths，并将点集的每一个维度分量视为cumulative\_chordal\_lengths的函数，由此进行给定的样条插值，得到最终结果。 

\section{Programing assingments A}
  使用A.json来输入所需要的插值区间的左右端点，插值点的个数，插值的边界条件和样条的阶数，在A.cpp内可以调整插值的方法为ppForm\_interpolation和Bspline\_interpolation。最后输出足够多个点的坐标来绘制图像，还支持最大误差的计算。
  \subsection*{ppForm\_interpolation}
  使用ppForm\_interpolation进行样条插值，得到的结果画出图像如下
  \begin{figure}[H]
  \begin{minipage}[t]{0.5\linewidth}
    \centering
    \includegraphics[scale = 0.42]{A_1_1.png}
  \end{minipage}
  \begin{minipage}[t]{0.5\linewidth}
    \centering
    \includegraphics[scale = 0.42]{A_3_1.png}
  \end{minipage}
  \caption{ppForm:线性插值和complete cubic spline}
  \label{fig1}
  \end{figure}
  \begin{figure}[H]
  \begin{minipage}[t]{0.5\linewidth}
    \centering
    \includegraphics[scale = 0.42]{A_3_2.png}
  \end{minipage}
  \begin{minipage}[t]{0.5\linewidth}
    \centering
    \includegraphics[scale = 0.42]{A_3_3.png}
  \end{minipage}
  \caption{ppForm:cubic spline with specifiedsecond derivatives at its end points和 natural cubic spline}
  \label{fig1}
\end{figure}
  \subsection*{Bspline\_interpolation}
  在使用Bspline\_interpolation进行样条插值时遇到错误： \\
\verb|A: /usr/local/include/eigen3/Eigen/src/Core/DenseCoeffsBase.h:366: Eigen::DenseoeffsBase<Derived, 1>::Scalar& Eigen::DenseCoeffsBase<Derived, 1>::operator()(Eigen::Index, Eigen::Index) [with Derived = Eigen::Matrix<double, -1, -1>; Eigen::DenseCoeffsBase<Derived, 1>::Scalar = double; Eigen::Index = long int]: Assertion `row >= 0 && row < rows() && col >= 0 && col < cols()' failed.Aborted |\\
无法解决。




\end{document}
